#include "CycleLinkList.h"

/**
 * 构造一个空的线性表
 */
Status CycleLinkList::InitList(void)
{
    /* 创建一个头结点, 并且使得L指向该头结点 */
    L = (LinkNode*)malloc(sizeof(LinkNode));
    if (L == nullptr)
        exit(OVERFLOW);

    /* 指针域名=指向头结点 */
    L->next = L;
    /** 注 ListHead为u循序列表的尾指针  */

    return OK;
}

/**
 * 销毁线性表
 */
Status CycleLinkList::DestoryList(void)
{
    LinkNode *q, *p;

    /* p指向头结点，先销毁链表中的元素 */
    p = L->next;
    while (p != L) {
        q = p->next;
        free(p);
        p = q;
    }
    /* 最后销毁头结点 */
    free(L);
    L = nullptr;

    return OK;
}
/**
 * 清空线性表
 */
Status CycleLinkList::ClearList(void)
{
    LinkNode *q, *p, *l;

    /* l指向头结点 */
    l = L->next;
    /* p指向第一个数据元素 */
    p = l->next;
    while (p != l) {
        q = p->next;
        free(p);
        p = q;
    }
    L->next = l;

    return OK;
}
/**
 * 线性表是否为空
 */
Status CycleLinkList::ListEmpty(void)
{
    if (L->next == L)
        return OK;
    else
        return FALSE;
}

/**
 * 线性表长度
 */
int CycleLinkList::ListLength(void)
{
    LinkNode *p;
    int count = 0;

    /* 指向头结点 */
    p = L->next;
    while (p != L) {
        count++;
        p = p->next;
    }

    return count;
}
/**
 * 获取线性表第i个位置的元素
 */
Status CycleLinkList::GetElem(int i, ElemType *e)
{
    LinkNode *p = L->next->next;
    int j = 0;

    if (i <0 || i > ListLength())
        return FALSE;

    while (j < i) {
        p = p->next;
        j++;
    }

    *e = p->e;

    return OK;
}
/**
 * 返回L中第1个与e满足关系compare()的数据元素的位置
 */
int CycleLinkList::LocateElem(ElemType e, Status(*compare)(ElemType, ElemType))
{
    int i = 0;
    LinkNode *p = L->next->next;

    // 没有到达头结点
    while (p != L->next) {
        i++;
        if (compare(p->e, e))
            return i;
        p = p->next;
    }

    return 0;
}
/**
 * 返回线性表前驱
 */
Status CycleLinkList::PriorElem(ElemType cur, ElemType *prev)
{
    // 指向第一个元素
    LinkNode *p = L->next->next;
    // 指向p的后继
    LinkNode *q = p->next;

    while (q != L->next) {
        if (q->e == cur) {
            *prev = p->e;
            return TRUE;
        }
        p = q;
        q = q->next;
    }

    return FALSE;
}
/**
 * 返回线性表后继
 */
Status CycleLinkList::NextElem(ElemType cur, ElemType *next)
{
    // 指向第一个元素
    LinkNode *p = L->next->next;

    while (p != L) {
        if (p->e == cur) {
            *next = p->next->e;
            return TRUE;
        }
        p = p->next;
    }
    return FALSE;
}
/**
 * 线性表第i个位置插入e
 */
Status CycleLinkList::ListInsert(int i, ElemType e)
{
    // p指向头结点
    LinkNode *p = L->next;
    int j =0;

    if (i < 0 || i > ListLength())
        return FALSE;

    while (j < i) {
        p = p->next;
        j++;
    }

    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->e = e;

    s->next = p->next;
    p->next = s;

    if (p == L)
        L = s;

    return OK;
}

/**
 * 删除线性表第i个位置元素
 */
Status CycleLinkList::ListDelete(int i, ElemType *e)
{
    // p指向头结点
    LinkNode *p = L->next, *q;
    int j = 0;

    if (i < 0 || i > ListLength())
        return FALSE;

    // 寻找i-1个节点的位置
    while (j < i) {
        p = p->next;
        j++;
    }
    // q指向待删除的节点
    q = p->next;
    p->next = q->next;
    *e = q->e;

    //删除的链尾的元素
    if (L == q)
        L = p;

    free(q);

    return OK;
}

/**
 * 遍历线性表
 */
Status CycleLinkList::ListTraverse(void)
{
    // p指向第一个元素
    LinkNode *p = L->next->next;

    while (p != L->next) {
        print(&p->e);
        p = p->next;
    }
    printf("\n");

    return OK;
}

/**
 * 合并两个线性表
 * 将线性表Lb中不在La中的数据元素插入到La中
 */
Status CycleLinkList::ListMerge(List *Lb)
{
    return OK;
}
/**
 * 头部插入节点
 */
Status CycleLinkList::ListHeadInsert(ElemType e)
{
    return OK;
}
/**
 * 尾部插入节点
 */
Status CycleLinkList::ListTailInsert(ElemType e)
{
    return OK;
}